package HashTable;//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 
//
// 示例 2: 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 10⁴ 
// s 和 p 仅包含小写字母 
// 
// Related Topics 哈希表 字符串 滑动窗口 👍 643 👎 0


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class findAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        /**
         * 双指针，滑动窗口
         * */

        int len = p.length(); //模式串的长度决定了滑动窗口的大小
        int n = s.length();  //文本串的长度
        List<Integer> res = new ArrayList<Integer>();
        //特殊情况，文本串长度小于模式串,不可能有
        if(n<len){
            return res;
        }
        //计数模式串的字符频率
        HashMap<Character, Integer> map = new HashMap<>();
        for (char ch: p.toCharArray()
             ) {
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        //滑动窗口遍历
        int left = 0, right = len-1;
        char[] chars = s.toCharArray();
        //首先将开始的【left,right】范围内的字符判断是不是异位词
        for (int i = left; i <= right; i++) {
            char ch = chars[i];
            if (map.containsKey(ch)){
                map.put(ch, map.get(ch)-1);
            }
        }
        if (check(map)){
            res.add(left);
        }
        //滑动窗口以固定窗口大小开始滑动
        right++;
        while(right<n){
            //左边移出去的字符如果再map中，则要还回去
            char l = chars[left++];
            if(map.containsKey(l)){
                map.put(l, map.get(l)+1);
            }
            //右边移动进来的字符如果再map中，则要减一次计数，否则不在就不可能是异位词
            char r = chars[right++];
            if(map.containsKey(r)){
                map.put(r, map.get(r)-1);
            }else{
                continue;
            }
            //如果滑动串口中的词都是模式串的字符，则检查是否是异位词
            if(check(map)){
                res.add(left);
            }
        }
        return res;

    }
    //如果计数中 有某个字符小于0，则这个范围不是异位词
    boolean check(HashMap<Character, Integer> map){
        for (char k: map.keySet()
             ) {
            if(map.get(k) != 0){
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
